# 奇偶链表： https://leetcode-cn.com/problems/odd-even-linked-list/submissions/


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# 自己的写法
class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        """
            这题我第一想法就是类似 头插法， 定义指针，每次跳两步，将节点插入头部后面，只是头部随着插入节点，更新。
            param:  pre: 表示排序中的最后一个奇数，也是头插法的头，当前奇数插入到其后
            param:  doubleNode： 表示当前奇数前面的偶数
            param:  cur: 代表当前奇数
            
            举例子 1 -> 2 -> 3 分别代表上述三者
        """
        if not head or not head.next or not head.next.next:
            return head
        pre = head
        cur = head.next.next
        doubleNode = pre.next

        # 注意： 这里移动两步和快慢指针的 循环条件不同，最后停在最后位置了，这里是停下来后，最后位置仍然要进行相关操作
        while cur:
            # 1. 临时变量 t 指向当前奇数节点， cur后移到下一个奇数节点
            t = cur
            # 2. doubleNode 指向当前奇数下一个偶数后， 更新为下一个偶数（下一个奇数的前一个）
            doubleNode.next = cur.next
            doubleNode = cur.next
            # 需判断是否还有后序
            if cur.next and cur.next.next:
                cur = cur.next.next
            else:
                cur = None

            # 头插法插入
            t.next = pre.next
            pre.next = t
            pre = t
        
        return head
